#include "Sudoku.h"
#include <time.h>
#include <vector>
using namespace std;

#include "cocos2d.h"
using namespace cocos2d;

int** Sudoku::GenerateSudoku() {
	int** arr = new int*[9];
	for (size_t i = 0; i < 9; i++)	
		arr[i] = new int[9];

	for (size_t i = 0; i < 9; i++)
	{
		for (size_t j = 0; j < 9; j++)
		{
			arr[i][j] = 0;
		}

	}

	vector<int>* cellValues = new vector<int>[81];
	for (size_t i = 0; i < 81; i++)
		for (size_t j = 1; j <= 9; j++)
			cellValues[i].push_back(j);

	srand(time(NULL));

	int count = 0;
	while (count < 81) {
		int rowIdx, colIdx;
		ConvertIndex(count, rowIdx, colIdx);
		int val = PickValue(count, cellValues[count], arr);
		if (val > 0) {
			arr[rowIdx][colIdx] = val;
			//CCLOG("[%d][%d]	= %d", rowIdx, colIdx, val);
			int index = FindIndex(val, cellValues[count]);
			if (index >= 0) {
				cellValues[count].erase(cellValues[count].begin() + index);
			}
			count++;
		}
		else {
			Rollback(count, cellValues[count], arr);
			count--;
		}
	}
	return arr;
}
void Sudoku::ConvertIndex(int index, int &row, int &col) {
	row = index / 9;
	col = index % 9;
}
int Sudoku::PickValue(int index, vector<int> value, int**sudoku) {
	int size = value.size();
	if (size <= 0) return 0;
	int pickIndex = rand() % size;
	int pickValue = value[pickIndex];
	int rowIdx, colIdx;
	ConvertIndex(index, rowIdx, colIdx);
	sudoku[rowIdx][colIdx] = pickValue;
	bool check = true;
	check &= CheckRow(index, sudoku);
	if (check == true) check &= CheckCol(index, sudoku);
	if (check == true) check &= CheckRegion(index, sudoku);
	if (check == true) { //Valid
		return pickValue;
	}
	else { //Fail	
		value.erase(value.begin() + pickIndex);
		sudoku[rowIdx][colIdx] = 0;
		return PickValue(index, value, sudoku);
	}
}
void Sudoku::Rollback(int index, vector<int>& value, int**sudoku) {
	value.clear();
	for (size_t i = 1; i <= 9; i++)	
		value.push_back(i);
	int rowIdx, colIdx;
	ConvertIndex(index, rowIdx, colIdx);
	sudoku[rowIdx][colIdx] = 0;
}
int Sudoku::FindIndex(int val, vector<int> values) {
	int index = -1;
	for (size_t i = 0; i < values.size(); i++)
	{
		if (values[i] == val) {
			index = i;
			break;
		}
	}
	return index;
}
bool Sudoku::CheckRow(int index, int**sudoku) {
	int rowIdx, colIdx;
	vector<int> checkVector;
	for (size_t i = 0; i < 9; i++)
		checkVector.push_back(i + 1);
	ConvertIndex(index, rowIdx, colIdx);
	for (size_t i = 0; i < 9; i++) {
		if (sudoku[rowIdx][i] == 0) continue;
		int checkVectorIndex = FindIndex(sudoku[rowIdx][i], checkVector);
		if (checkVectorIndex < 0)
			return false;
		checkVector.erase(checkVector.begin() + checkVectorIndex);
	}		
	return true;
}
bool Sudoku::CheckCol(int index, int**sudoku) {
	int rowIdx, colIdx;
	vector<int> checkVector;
	for (size_t i = 0; i < 9; i++)
		checkVector.push_back(i + 1);
	ConvertIndex(index, rowIdx, colIdx);
	for (size_t i = 0; i < 9; i++) {
		if (sudoku[i][colIdx] == 0) continue;
		int checkVectorIndex = FindIndex(sudoku[i][colIdx], checkVector);
		if (checkVectorIndex < 0)
			return false;
		checkVector.erase(checkVector.begin() + checkVectorIndex);
	}
	return true;
}
bool Sudoku::CheckRegion(int index, int**sudoku) {
	int rowIdx, colIdx;
	vector<int> checkVector;
	for (size_t i = 1; i <= 9; i++)
		checkVector.push_back(i);
	ConvertIndex(index, rowIdx, colIdx);
	Normalize(rowIdx, colIdx);
	for (int i = -1; i < 2; i++) {
		for (int j = -1; j < 2; j++) {
			if (sudoku[rowIdx + i][colIdx + j] == 0) continue;
			int checkVectorIndex = FindIndex(sudoku[rowIdx + i][colIdx + j], checkVector);
			if (checkVectorIndex < 0)
				return false;
			int b = checkVector.size();
			checkVector.erase(checkVector.begin() + checkVectorIndex);
			int a = checkVector.size();		
		}
	}	
	return true;
}
void Sudoku::Normalize(int& rowIdx, int& colIdx) {
	int **arr = new int*[9];

	for (size_t i = 0; i < 9; i++)
	{
		arr[i] = new int[2];
	}
	arr[0][0] = 1;
	arr[0][1] = 1;
	arr[1][0] = 1;
	arr[1][1] = 4;
	arr[2][0] = 1;
	arr[2][1] = 7;
	arr[3][0] = 4;
	arr[3][1] = 1;
	arr[4][0] = 4;
	arr[4][1] = 4;
	arr[5][0] = 4;
	arr[5][1] = 7;
	arr[6][0] = 7;
	arr[6][1] = 1;
	arr[7][0] = 7;
	arr[7][1] = 4;
	arr[8][0] = 7;
	arr[8][1] = 7;

	for (size_t i = 0; i < 9; i++)
	{
		int newRowIdx = rowIdx - arr[i][0];
		int newColIdx = colIdx - arr[i][1];
		if (abs(newRowIdx) <= 1 && abs(newColIdx) <= 1)
		{
			rowIdx = arr[i][0];
			colIdx = arr[i][1];
			break;
		}
	}

	for (int i = 0; i < 9; i++)
		delete arr[i];
	delete arr;
}